package main

import "math"

//暴力递归
//min(子问题)
func main() {
	coins := []float64{1, 2, 3, 5}
	amount := float64(8)

	res := clq(coins, amount)
	println(res)
}

var men = make(map[float64]float64)

func clq(coins []float64, amount float64) float64 {
	//base case
	if amount < 0 {
		return -1
	}
	if amount == 0 {
		return 0
	}
	if _, ok := men[amount]; ok {
		return men[amount]
	}

	res := math.MaxFloat64
	for _, coin := range coins {
		subQ := clq(coins, amount-coin)
		if subQ == -1 {
			continue
		}
		res = math.Min(float64(res), float64(subQ)+1)
	}
	men[amount] = res
	return res
}
